"""
3186. 施咒的最大总伤害
中等
相关标签
相关企业
提示
一个魔法师有许多不同的咒语。

给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。

已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。

每个咒语最多只能被使用 一次 。

请你返回这个魔法师可以达到的伤害值之和的 最大值 。



示例 1：

输入：power = [1,1,3,4]

输出：6

解释：

可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。

示例 2：

输入：power = [7,1,6,6]

输出：13

解释：

可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。



提示：

1 <= power.length <= 105
1 <= power[i] <= 109
"""
from collections import Counter
from functools import cache


class Solution(object):
    def maximumTotalDamage(self, power: list[int]) -> int:
        cnt = Counter(power)
        a = sorted(cnt.keys())
        @cache
        def dfs(i: int) -> int:
            if i < 0:
                return 0
            x = a[i]
            j = i
            while j and a[j - 1] >= x - 2:
                j -= 1
            return max(dfs(i - 1), dfs(j - 1) + x * cnt[x])

        return dfs(len(a) - 1)

    def maximumTotalDamage_Err1(self, power):
        """
        :type power: List[int]
        :rtype: int
        """
        l = len(power)
        dp = [0] * int(1e9 + 1)
        nums = [0] * int(1e9 + 1)

        for i in range(l):
            nums[power[i]] += power[i]
        dp[1] = nums[1]
        dp[2] = max(nums[1],nums[2])
        for i in range(2, int(1e5 + 1)):
            dp[i] = max(dp[i - 1], dp[i - 3] + nums[i])
        return max(dp[int(1e5)],dp[int(1e5) - 1],dp[int(1e5) - 2])

if __name__ == '__main__':
    print(Solution().maximumTotalDamage([7,1,6,6]))
    print(Solution().maximumTotalDamage([1,1,3,4]))
    print(Solution().maximumTotalDamage([1,1,1,1]))
    for x,y in enumerate(['a','b','c']):
        print(x,y)